﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.Utils;
using Lists = Algoritmia.DataStructures.Lists;

namespace Algoritmia.Problems.Geometry.ConvexMin
{
    public class ConvexMinFinder1<T> : IConvexSequenceMinFinder<T>
    {
        private readonly Comparison<T> _comparison;
        private readonly Func<IEnumerable<T>, Lists.IList<T>> _createList;

        public ConvexMinFinder1(Comparison<T> comparison = null, Func<IEnumerable<T>,Lists.IList<T>> createList = null)
        {
            _comparison = AlgoritmiaFactory.GetDefaultComparison(comparison);
            _createList = createList ?? (o => AlgoritmiaFactory.Lists<T>.BuildDefault(o));
        }

        #region Implementation of IConvexSequenceMinFinder<T>

        public T Min(Lists.IList<T> list)
        {
            if ( list.Count > 2)
            {
                int j = list.Count/2;
                
                if (_comparison(list[j-1],list[j]) >= 0)
                {
                    return Min(_createList(list.Where((e, i) => i >= j)));
                }
                return  Min(_createList(list.Where((e, i) => i < j)));
            }
            if ( list.Count == 1)
            {
                return list[0];
            }
            if ( list.Count == 2)
            {
                return _comparison(list[0], list[1]) < 0 ? list[0] : list[1];
            }
            throw new InvalidOperationException("Is not possible to find the minimum element of an empty sequence");
        }

        #endregion
    }
}
